package com.yulan.backTrack;

import org.junit.Test;

/**
 * 矩阵中的路径
 */
public class Offer_12 {
    public boolean hasPath(char[] matrix1, int rows, int cols, char[] str) {
        char[][] matrix = new char[rows][cols];
        for(int i = 0;i<rows;i++){
            for(int j = 0;j<cols;j++){
                matrix[i][j] = matrix1[i*cols + j ];
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
        char[] words = str;
        for(int i = 0 ;i< matrix.length; i++){
            for(int j = 0; j<matrix[0].length; j++){
                if(dfs(matrix,i,j,0,words)) return true;
            }
        }

        return false;

    }

    public boolean dfs(char[][] matrix, int i, int j, int k, char[] word){
        if(i<0 || i>= matrix.length || j<0 || j>=matrix[0].length || matrix[i][j] != word[k])
            return false;
        if(k == word.length-1)
            return true;

        char tmp = matrix[i][j];
        matrix[i][j] = '/';

        boolean res = dfs(matrix,i+1,j,k+1,word) || dfs(matrix,i-1,j,k+1,word) ||
                dfs(matrix,i,j+1,k+1,word) || dfs(matrix,i,j-1,k+1,word);

        matrix[i][j] = tmp;
        return res;
    }

    @Test
    public void test(){
        String str = "ABCESFCSADEE";
        char[] chars = str.toCharArray();
        char[] path = "ABCCED".toCharArray();
        System.out.println(hasPath(chars,3,4,path));

    }
}
